Search Results

Documents authored by Venkitesh, S.

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.42
On the Probabilistic Degree of an n-Variate Boolean Function

Authors: Srikanth Srinivasan and S. Venkitesh

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
Nisan and Szegedy (CC 1994) showed that any Boolean function f:{0,1}ⁿ → {0,1} that depends on all its input variables, when represented as a real-valued multivariate polynomial P(x₁,…,x_n), has degree at least log n - O(log log n). This was improved to a tight (log n - O(1)) bound by Chiarelli, Hatami and Saks (Combinatorica 2020). Similar statements are also known for other Boolean function complexity measures such as Sensitivity (Simon (FCT 1983)), Quantum query complexity, and Approximate degree (Ambainis and de Wolf (CC 2014)). In this paper, we address this question for Probabilistic degree. The function f has probabilistic degree at most d if there is a random real-valued polynomial of degree at most d that agrees with f at each input with high probability. Our understanding of this complexity measure is significantly weaker than those above: for instance, we do not even know the probabilistic degree of the OR function, the best-known bounds put it between (log n)^{1/2-o(1)} and O(log n) (Beigel, Reingold, Spielman (STOC 1991); Tarui (TCS 1993); Harsha, Srinivasan (RSA 2019)). Here we can give a near-optimal understanding of the probabilistic degree of n-variate functions f, modulo our lack of understanding of the probabilistic degree of OR. We show that if the probabilistic degree of OR is (log n)^c, then the minimum possible probabilistic degree of such an f is at least (log n)^{c/(c+1)-o(1)}, and we show this is tight up to (log n)^{o(1)} factors.
Cite as

Srikanth Srinivasan and S. Venkitesh. On the Probabilistic Degree of an n-Variate Boolean Function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{srinivasan_et_al:LIPIcs.APPROX/RANDOM.2021.42,
  author =	{Srinivasan, Srikanth and Venkitesh, S.},
  title =	{{On the Probabilistic Degree of an n-Variate Boolean Function}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.42},
  URN =		{urn:nbn:de:0030-drops-147356},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.42},
  annote =	{Keywords: truly n-variate, Boolean function, probabilistic polynomial, probabilistic degree}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.28
On the Probabilistic Degrees of Symmetric Boolean Functions

Authors: Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
The probabilistic degree of a Boolean function f:{0,1}^n -> {0,1} is defined to be the smallest d such that there is a random polynomial P of degree at most d that agrees with f at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees of Boolean functions - specifically symmetric Boolean functions - have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems. In this paper, we characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors over all fields of fixed characteristic (positive or zero).
Cite as

Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. On the Probabilistic Degrees of Symmetric Boolean Functions. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{srinivasan_et_al:LIPIcs.FSTTCS.2019.28,
  author =	{Srinivasan, Srikanth and Tripathi, Utkarsh and Venkitesh, S.},
  title =	{{On the Probabilistic Degrees of Symmetric Boolean Functions}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.28},
  URN =		{urn:nbn:de:0030-drops-115908},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.28},
  annote =	{Keywords: Symmetric Boolean function, probabilistic degree}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact